package com.ocean.tree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * https://leetcode.cn/problems/n-ary-tree-level-order-traversal/
 * n 叉树的层次遍历
 */
public class NAryTreeLevelOrderTraversal2 {

    public static void main(String[] args) {
        NAryTreeLevelOrderTraversal2 traversal = new NAryTreeLevelOrderTraversal2();
        Node root = Node.getRoot();
        List<List<Integer>> res = traversal.levelOrder(root);
        System.out.println(res);
    }

    /**
     * [[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]
     * <p>
     * 广度优先搜索
     *
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> res = new ArrayList<>();
        Deque<Node> deque = new LinkedList<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            List<Integer> curList = new ArrayList<>();
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                Node cur = deque.poll();
                curList.add(cur.getVal());
                if (cur.children != null && !cur.children.isEmpty()) {
                    for (Node each : cur.children) {
                        deque.offer(each);
                    }
                }

            }
            res.add(curList);
        }
        return res;
    }
}
